package indi.book.chapter_1_1_basicProgramModel;

import org.junit.Test;

/**
 * Created by lazyo on 2018/3/4.
 */
public class Ex_22_to_25_binarySearch {


    /**
     * 使用1.1.6.4节中的rank()递归方法重新实现BinarySearch并跟踪该方法的调用.每当该方法被调用时,
     * 打印出它的参数low和high并按照递归的深度缩进.
     * @param key
     * @param arr
     * @return
     */
    @Test
    public static int ex_22(int key,int[] arr){
        return ex_22(key,arr,0,arr.length - 1,0);
    }

    public static int ex_22(int key,int[] arr,int low,int high,int depth){
        for (int i = 0; i < depth; i++) {
            System.out.printf("    ");
        }
        System.out.printf("low = %d, high = %d \n",low,high);
        int mid = low + (high - low)/2;
        if(low > high){
            return -1;
        }
        if(arr[mid] == key){
            return mid;
        }else if(arr[mid] > key){
            high = mid - 1;
        }else {
            low = mid + 1;
        }
        return ex_22(key,arr,low,high,++depth);
    }

    public static void main(String[] args) {
//        System.out.println("请输入key:");
//        int key = StdIn.readInt();
//        int[] arr = new int[6];
//        for (int i = 0; i < arr.length; i++) {
//            System.out.printf("请输入第%d个数:\n",i);
//            arr[i] = StdIn.readInt();
//        }
        int key = 15;
        int[] arr = {1,2,3,5,6,6,7,9,10};
        int res = ex_22(key,arr);
        System.out.println(res);
    }
}
